package labirynthPackage;

import java.io.IOException;
import java.util.*;
import java.math.*;

/**
 *
 * @author Biserova Ekaterina, Baburkina Anastasia, Perminov Alexander
 */

public class Labyrinth {
    Field field;
    Robot robot;
    
    int Score;
    /**
     * Количество собранных лямбд
     */
    int countOfL;
    /**
    *  Внутренний класс ребро, нужен для глобального поиска
    */
    static class Edge implements Comparable<Edge> {
        int a, b, cost;

        public Edge(int a, int b, int cost) {
          this.a = a;
          this.b = b;
         this.cost = cost;
        }

        @Override
        public int compareTo(Edge t) {
            if (this.cost<t.cost) {
                return -1;
            } 
            else {
                if (this.cost>t.cost) {
                    return 1;
                }
                else {
                    return 0;
                }
            } 
        }
     }

    
    public Labyrinth() throws IOException{
        field = new Field("in.txt");
        robot = new Robot(field.robotPos);
        countOfL = 0;
    }
    
    /**
     * Проверяем, можно ли двигаться в эту точку, т.е. нет ли там стены или камня
     * @param p
     * @return 
     */
    private boolean checkPoint(Point p){
        switch(field.getCell(p))
        {
            case Stone:
                return false;
            case Wall:
                return false;
            case Close:
                return false;
            default:
                return true;
        }
    }
    /**
     * Метод делает проверку, можно ли из точки p пойти в направлении dir
     * @param p - точка, откуда движемся
     * @param dir - направление, в котором движемся
     * @return true/false в зависимости от того, можно переместиться или нельзя.
     */
    private boolean checkMove(Point p, Direction dir){
        Point newP = new Point(p.y, p.x);
        newP.move(dir);
        //Случай, когда робот может подвинуть камень (полностью реализован в Field)
        if(field.robotMovesStone(newP, dir)){
            return true;
        }
        //обычное движение
        if(checkPoint(newP)){
            return true;
        }else{
            return false;
        }
    }
    /**
     * Переводим тип ячейки в символ
     * @param T - тип ячейки
     * @return символ, соответсвующий типу T
     */
    public String convertCellToChar(CellType T){
        switch (T){
            case Stone:
                return "*";
            case Wall:
                return "#";
            case Ground:
                return "."; 
            case Close:
                return "X";
            case Open:
                return "O";
            case A:
                return "A";
            case Empty:
                return " ";
            default:
                return " ";
        }
    }
    /**
     * Переводим символы в команды робота
     * @param S - символ, введенный пользователем с клавиатуры.
     * @return Одну из команд робота, присутсвующих в перечиcлении Direction
     */
    public Direction convertCharToDir(String S){
        switch (S){
            case "U":
                return Direction.Up;
            case "D":
                return Direction.Down;
            case "L":
                return Direction.Left;
            case "R":
                return Direction.Right;
            case "A":
                return Direction.Abort;
            case "W":
                return Direction.Wait;
            default: 
                return Direction.Wait;
        }
    }
    /**
     * Получает команду для робота, проверяет, можно ли из точки, 
     * где находится робот, переместиться в указанном направлении,
     * и выполняет перемещение, если возможно.
     * @param S - символ с командой роботу
     * @return true - если совершаем перемещение роботом, и false - если не совершаем
     */
    public boolean move(String S){
        Direction dir;
        dir = convertCharToDir(S);
        if (dir == Direction.Abort){
            return false;
        }
        else 
            if(dir == Direction.Wait){
                return true;
            }
            else 
                if (checkMove(robot.getPos(), dir)){
                    field.cleanGround(robot.getPos());
                    robot.move(dir);
                    //вычитаем 1 балл за ход
                    this.Score--;
                    if (field.checkL(robot.getPos())){
                        countOfL++;
                        //добавляем 25 очков за лямбду
                        this.Score+=25;
                        if(countOfL>=field.numOfL){
                            field.openExit();
                        }
                    }
                    return true;
                }
                else{
                    return false;
                }
    }
    /**
     * @return true, если зашли в открытый выход и false в любом другом случае 
     */
    public boolean isExit(){
        Point p = new Point(robot.getPos().y,robot.getPos().x);
        if (field.getCell(p)==CellType.Open){
            Score+=countOfL*50;
            return true;
        }
        else{
            return false;
        }
    };
    /**
     * Заставляет пройти робота по пути
     * @param way - путь
     * @return true/false в зависимости от того, прошел робот путь или нет
     */
    public boolean robotGoesTo(Way way, Way correctedWay, Point finishPoint) {
        while (!robot.getPos().equals(finishPoint)) {
            //Передвигаем робота
            move(Character.toString(way.road.charAt(0)));
            //Если, пока робот шел, на него упал камень, возвращаем false
            if (field.step(robot.getPos())) {
                return false;
            }
            //Если робот достиг выхода, возвращаем true
            if (isExit()){
                return true;
            }
            //Записываем очередную клетку итогового пути (станет другим, когда допишем обход камней) 
            correctedWay.road+=way.road.charAt(0);
            
            //Ищем путь заново, так как камни могли изменить положение или робот мог их подвинуть
            way.road = field.AStar(robot.getPos(), finishPoint);
            if(way.road=="Z"){
                correctedWay.road+="A";
                return true;
            }
            
            //Если найденные в AStar на последней итерации путь по длине равен 1, то добавляем этот ход к конечному пути
            if(!way.road.isEmpty()){
                if(way.road.length()==1){
                    correctedWay.road+=way.road.charAt(0);
                }
            }
            
            //System.out.println(correctedWay.toString());
            //System.out.println(toString());
        }
        return true;
    }
    public Way globalFind() {
        
        /*
         * Простой поиск - путь до ближайшей лямбды
         */
        //создаем список всех лямбд
        LinkedList<Integer> lambdas = new LinkedList<Integer>();
        for (int i=1; i<field.numOfL+1; i++){
            lambdas.add(i);
        }
        //создаем переменную, где будем хранить минимальный путь
        String minWay = new String("");
        //Пропустили ли мы лямбду
        boolean isWaisted = false;
        //индекс ближайщей лямбды
        int lInd = 1;
        //Итоговый путь, который вернет функция
        Way finalWay = new Way();
        
        while(!lambdas.isEmpty())
        {
            //Делает минимальный путь оооооочень длинным
            minWay = "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW";
            //находим путь от робота до всех по очереди лямбд, входящих в открытый список
            for(int i=1; i<field.numOfL+1; i++){
                if(lambdas.contains(i)){
                    String temp = field.AStar(robot.getPos(), field.prizes[i]);
                    //сохраняем минимальный
                    /*if(temp!="Z" & temp.length()<minWay.length()){
                        minWay=new String(temp);
                        lInd = i;
                    }*/
                    if(temp!="Z"){
                        //собирание лямбды, над которой камень, считаем несколько менее приоритетным.
                        if(field.getCell(new Point(field.prizes[i].y-1, field.prizes[i].x))==CellType.Stone){
                            if(temp.length()+40<minWay.length()){
                                minWay=new String(temp);
                                lInd = i;
                            }
                        }else if(temp.length()<minWay.length()){
                            minWay=new String(temp);
                            lInd = i;
                        }
                        
                    }
                    if(temp=="Z"){
                        lambdas.remove(lambdas.indexOf(i));
                        isWaisted = true;
                    }
                }
            }
            
            if(!lambdas.isEmpty()){
                lambdas.remove(lambdas.indexOf(lInd));
            }
            //запускаем робота
            Way way = new Way();
            Way correctedWay = new Way(); //путь, который вернет функция robotGoesTo после прохождения
            way.road = new String(minWay);
            //Если робот не умер в процессе, добавляем этот путь, если-таки умер - делаем аборт
            if(robotGoesTo(way, correctedWay, field.prizes[lInd])){
                finalWay.road+=correctedWay.road;
            }else{
                finalWay.road+="A";
                return finalWay;
            }
        }
        //Если мы пропустили какую-то лямбду, не собирая её, делаем аборт, так как нет смысла идти к выходу
        if(isWaisted){
            finalWay.road+="A";
            return finalWay;
        }
        //Когда мы собрали все лямбды, ищем путь до выхода аналогичным способом.
        Way temp = new Way(); //Переменная, в которую запишем путь
        temp.road = field.AStar(robot.getPos(), field.exit);
        if(temp.road=="Z"){
            finalWay.road+="A";
            return finalWay;
        }
        //запускаем робота
        Way correctedWay = new Way(); //путь, который вернет функция robotGoesTo после прохождения
        //Если робот не умер в процессе, добавляем этот путь, если-таки умер - делаем аборт
        if(robotGoesTo(temp, correctedWay, field.exit)){
           finalWay.road+=correctedWay.road;
        }else{
           finalWay.road+="A";
        }   
        return finalWay;
        
        /*
        String[][] cost = new String[field.numOfL+1][field.numOfL+2];
        for (int i=1; i<field.numOfL+1; i++) {
            //Ищем пути от старта до лямбд
             cost[0][i] = field.AStar(robot.getPos(), field.prizes[i]);
             // Ищем пути от выхода к лямбдам
             cost[i][field.numOfL+1] = field.AStar(field.prizes[i], field.exit);
             //Ищем пути от каждой лямбде к каждой
             for (int j=1; j<i; j++) {
                 cost[j][i] = field.AStar(field.prizes[i], field.prizes[j]);
             }
        }
        //Ищем путь от робота к выходу
        cost[0][field.numOfL+1] = field.AStar(robot.getPos(), field.exit);
        int n = cost.length;
        */
        /*
        //Создаем список ребер
        List<Edge>[] edges = new List[n];
        //Заполняем список ребер
        for (int i = 0; i < n; i++) {
            edges[i] = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (cost[i][j].length() != 0) {
                    edges[i].add(new Edge(j, cost[i][j].length()));
                }
            }
        }*/
        /*
        //СОздаем массив ребер с количеством элементов над диагональю квадратной матрицы n*n
        //Исключая первую строку и последний столбец
        int numOfEdge = (n-1)*(n-4)/2+1;
        Edge[] allEdges = new Edge[numOfEdge];
        //Заполняем массив
        int k =0;
        for (int i=1; i<n; i++){
            for (int j = 1; j < n; j++) {
                if (cost[i][j].length() != 0) {
                    allEdges[k] = new Edge(i, j, cost[i][j].length());
                    k++;
                }
            }
        }
        //Сортируем ребра по весу
        Arrays.sort(allEdges);
        //Создаем список ребер. Индекс этого массива - вершина, с которой соединяем
        //А в списке хранятся соединенные с ней вершины
        LinkedList<Integer>[] edges = new LinkedList[n];
        //В дереве храним вершины и соединенный с ней вершины
        for(int p=0; p<numOfEdge; p++) {
            if(!edges[allEdges[p].a].contains(allEdges[p].b)){
                edges[allEdges[p].a].add(allEdges[p].b);
                edges[allEdges[p].b].add(allEdges[p].a);
            }
        }*/
        
        //return new Way();
    }

    //Должен выводить поле field и робота на соответсвующих координатах.
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder(); 
        for (int i=0; i<field.height; i++){
            for (int j=0; j<field.width; j++){
                Point p = new Point(i,j);
                if ((robot.getPos().x == p.x)&&(robot.getPos().y == p.y)){
                    sb.append("R");
                }
                else{
                    if(field.getCell(p)!=null){
                        sb.append(convertCellToChar(field.getCell(p)));
                    }
                }
            }
            sb.append('\n');
        }
        return sb.toString();
    }
}